//每个数据在链表结点中的结构
struct Node
{
    int key,val,freq;
    Node(int k,int v,int f):key(k),val(v),freq(f){}
};
class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    
   /*
   key_table是一个哈希表。其中key存数据中的key,value存list结点的迭代器
   fre_table是一个哈希表。其中key存次数，value存双链表list,每一个频数对应一个list
   插入数据时，case1:如果缓存中没有待插入的数据，并且还有容量，就将该数据挂在频数为1的list链表上，
   并创建key_table中key为该数据的key,value为指向list上的新结点的迭代器
   case2:如果缓存中没有待插入的数据，容量已满，找到频数最小的那条链表，删除掉尾部元素，对应删除
   key_table中key和value，如果删除完后该频次的链表为空，就删除fre_table中key.
   有容量了以后就是case1
   case3:如果缓存中有这个数据的key，该数据的频数加1，将该数据挂载到对应频次的链表上，将原链表上的结点
   删除，修改key_table中value，让它指向正确的链表结点
   获取数据时，和上面的case3差不多
   */
    int minfreq=0;
    unordered_map<int, list<Node>::iterator>key_table;
    unordered_map<int, list<Node>>freq_table;
    void set(int key,int val,int cap)
    {
        if(cap==0) return;
        auto it=key_table.find(key);
        if(it==key_table.end())
        {
            if(key_table.size()==cap) //空间不足case2
            {
                auto it=freq_table[minfreq].back();
                key_table.erase(it.key);
                freq_table[minfreq].pop_back();
                if(freq_table[minfreq].size()==0)
                    freq_table.erase(minfreq);
            }
            freq_table[1].push_front(Node(key,val,1));
            key_table[key]=freq_table[1].begin();
            minfreq=1;
        }else//找到了
        {
            auto it=key_table[key];
            int freq=it->freq;
            freq_table[freq].erase(it);
            if(freq_table[freq].size()==0)
            {
                freq_table.erase(key);
                if(minfreq==freq)
                    minfreq++;
            }
            freq_table[freq+1].push_front(Node(key,val,freq+1));
            key_table[key]=freq_table[freq+1].begin();
        }
    }
    int get(int key)
    {
        auto it=key_table.find(key);
        if(it==key_table.end()) return -1;
        list<Node>::iterator node=it->second;
        int value=node->val;
        int freq=node->freq;
        freq_table[freq].erase(node);
        if(freq_table[freq].size()==0)
        { 
            freq_table.erase(freq);
            if(minfreq==freq)
                minfreq+=1;
        }
        freq_table[freq+1].push_front(Node(key,value,freq+1));
        key_table[key]=freq_table[freq+1].begin();
        return value;
    }
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int >ans;
        for(auto x:operators)
        {    
            if(x[0]==1) set(x[1], x[2], k);
            else
                ans.push_back(get(x[1]));
        }
        return ans;
    }
};